package arithmetic2.day01;

/*
   ^(异或):满足交换律和结合律
   两个相同的数异或=0
 */
public class Demo01 {
    public static void main(String[] args) {
//        int a = 10;
//        int b = 20;
//        a = a ^ b;
//        b = a ^ b;
//        a = a ^ b;
//        System.out.println(a);
//        System.out.println(b);

//        oddNum(new int[]{2,2,3,2,4,6,4,2,6});

        doubleOddNum(new int[]{2,2,3,2,4,6,4,2,6,5});
    }

    //交换两个数
    public static void swap(int arr[],int i,int j){
        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }

    //一个数组中有一个数出现了奇数次，其他数都出现了偶数次，求这个数
    public static void oddNum(int arr[]){
        int eor = 0;
        for(int num : arr){
            eor = eor^num;
        }
        System.out.println(eor);
    }

    //一个数组中有两个数出现了奇数次，其他数都出现了偶数次，求这两个数(a,b)
    public static void doubleOddNum(int arr[]){
        int eor = 0;
        for(int num : arr){
            eor = eor^num;
        }
        //此时eor = a ^ b     ~:二进制取反
        //因为a!=b 所以 eor!=0 那么eor的二进制表示中必然有一位是1
        int rightOne = eor & (~eor+1);  //提取出eor最右侧的1

        int onlyOne = 0;
        for(int num : arr){
            if((num & rightOne) == 0){  //将与rightOne上1的位置不一样的数都与onlyOne异或
                onlyOne ^= num;
            }
        }
        System.out.println(onlyOne);
        System.out.println(onlyOne ^ eor);
    }
}
